ArrayList扩容详解

2023-12-09 00:38| 来源: 网络整理| 查看: 265

本文探讨一下ArrayList的扩容过程

ArrayList底层是数组elementData，用于存放插入的数据。初始大小是0，当有数据插入时，默认大小DEFAULT_CAPACITY = 10。如果在创建ArrayList时指定了initialCapacity，则初始大小是ArrayList

1. 验证扩容的代码示例

从示例中可以看到，当添加元素时，如果元素个数+1> 当前数组长度【size + 1 > elementData.length】时，进行扩容，扩容后的数组大小是： oldCapacity + (oldCapacity >> 1)

将旧数组内容通过Array.copyOf全部复制到新数组，此时新旧列表的size大小相同，但elementData的长度即容量不同

注意：扩容并不是严格的1.5倍，是扩容前的数组长度右移一位 + 扩容前的数组长度

public class SimpleTest { public static void main(String[] args) { ArrayList list = new ArrayList(); int size = 0; for (int i = 0; i < 100; i++) { list.add(i); if(getCapacity(list)>size) { System.out.println("capacity:"+getCapacity(list) + ",size:"+list.size()); size = getCapacity(list); } } } public static Integer getCapacity(ArrayList list) { Integer length = null; Class clazz = list.getClass(); Field field; try { field = clazz.getDeclaredField("elementData"); field.setAccessible(true); Object[] object = (Object[]) field.get(list); length = object.length; return length; } catch (Exception e) { e.printStackTrace(); } return length; } }

运行结果如下：

capacity:10,size:1 capacity:15,size:11 capacity:22,size:16 capacity:33,size:23 capacity:49,size:34 capacity:73,size:50 capacity:109,size:74

2. 扩容相关的源代码 public boolean add(E e) { //调用了一ensureCapacityInternal方法，确保数组下标不越界 ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //新容量扩大到原容量的大约1.5倍，右移一位相当于原数值除以2，扩容并不是严格的1.5位 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); } 3. 为什么按大约1.5倍扩容

扩容因子的大小选择，需要考虑如下情况：

扩容容量不能太小，防止频繁扩容，频繁申请内存空间 + 数组频繁复制

扩容容量不能太大，需要充分利用空间，避免浪费过多空间；

为了能充分使用之前分配的内存空间，最好把增长因子设为 1

【本文地址】

公司简介

联系我们